package com.jxb.three;

import java.util.Arrays;

/**
 * 寻找两个正序数组的中位数
 *  * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 *  * 请你找出并返回这两个正序数组的 中位数 。
 *
 *  思路：
 *      使用二分查找法，找出对应的中间值
 *
 *
 * @author jiaobo
 * @date Created in 2024/12/27 20:50
 **/
public class Medianof2SortedArrays_4 {

    public static void main(String[] args) {
        int[] num1 = {1,3};
        int[] num2 = {2,4};
        System.out.println(findMedianSortedArrays(num1, num2));
        // System.out.println((4+6+1)/2);
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int left = (m+n+1)/2;
        int right = (m+n+2)/2;
        return (getkth(nums1,0,nums2,0,left) + getkth(nums1,0,nums2,0,right)) / 2.0;
    }

    public static double getkth(int[] nums1, int nums1Start, int[] nums2, int nums2Start, int k) {
        /*有任何一个数组空了，直接返回另外一个非空数组的中位数结果*/
        if (nums1Start > nums1.length - 1)
            return nums2[nums2Start + k - 1];
        if (nums2Start > nums2.length - 1)
            return nums1[nums1Start + k - 1];
        /*找第1小的数字，所以只需判断两个数组中第一个数字哪个小就可以了*/
        if (k == 1)
            return Math.min(nums1[nums1Start], nums2[nums2Start]);
        /*获得两个数组中第k/2个元素的值*/
        int num1Mid = Integer.MAX_VALUE, num2Mid = Integer.MAX_VALUE;
        if (nums1Start + k/2 - 1 < nums1.length)
            num1Mid = nums1[nums1Start + k/2 - 1];
        if (nums2Start + k/2 - 1 < nums2.length)
            num2Mid = nums2[nums2Start + k/2 - 1];

        /*比较两值的大小，然后以递归的形式继续更小数组的处理*/
        if (num1Mid < num2Mid)
            /*num1Mid更小，排除num1[]中小于等于num1Mid的部分*/
            return getkth(nums1, nums1Start + k/2,
                          nums2, nums2Start,k - k/2);
        else
            /*num2Mid更小，排除num2[]中小于等于num2Mid的部分*/
            return getkth(nums1, nums1Start, nums2,
                          nums2Start + k/2, k - k/2);
    }

    // private static double findMidValue(int[] nums1, int[] nums2, int mid, int index) {
    //     if (index == 1) {
    //         if (nums1.length == 0) {
    //             return nums2[0];
    //         }else
    //         //获取中位数
    //         return (nums1[0] + nums2[0]) / 2;
    //     }
    //     int newIndex = (index - mid)/2;
    //     if (nums1[index] < nums2[index]) {
    //         int[] newNum1 = Arrays.copyOfRange(nums1,index+1,nums1.length-1);
    //         findMidValue(newNum1,nums2,mid,newIndex);
    //     }else {
    //         int[] newNum2 = Arrays.copyOfRange(nums2,index+1,nums2.length-1);
    //         findMidValue(nums1,newNum2,mid,newIndex);
    //     }
    //     return 0;
    // }

}
